package _10_binary_tree.order.scope;

import _04_queue.Queue;
import _04_queue.my_implements.ArrayQueue;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/6 - 12:09
 * 二叉数广度优先遍历 每一层都是从左向右
 */
public class LevelOrderTest {
    /*

           1
          / \
         2   3
        /\   /\
       4  5 6  7

       遍历得到的结果：1 2 3 4 5 6 7
     */
    @Test
    public void test() {
        // 构建树节点
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4),
                        new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),
                        new TreeNode(7)));

//        List list = foreachTreeNode(root);
//        System.out.println(list);
//        printTree(root);

        List<List<Integer>> nestList = listorder(root);
        System.out.println(nestList);
    }

    /**
     * 基于自定义队列实现
     * @param root
     */
    List foreachTreeNode(TreeNode root) {
        if(root == null) {
            return Collections.emptyList();
        }
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayQueue<>(16);
        queue.offer(root);

        while (!queue.isEmpty()) {
            // 得到树节点
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }

        return list;
    }

    /**
     * 打印树形结构
     * 1
     * 2	3
     * 4	5	6	7
     * @param root
     */
    void printTree(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new ArrayQueue<>(16);
        queue.offer(root);

        int c1 = 1;
        while (!queue.isEmpty()) {
            int c2 = 0;
            for (int i = 0; i < c1; i++) {
                // 得到树节点
                TreeNode node = queue.poll();
                System.out.print(node + "\t");
                if(node.left != null) {
                    queue.offer(node.left);
                    c2++;
                }
                if(node.right != null) {
                    queue.offer(node.right);
                    c2++;
                }
            }
            c1 = c2;
            System.out.println();
        }
    }

    /**
     * 使用两层 nest list收集树
     * @param root
     * @return
     */
    List<List<Integer>> listorder(TreeNode root) {
        java.util.Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        ArrayList<List<Integer>> outerList = new ArrayList<>();

        while (!queue.isEmpty()) {
            ArrayList<Integer> innerList = new ArrayList<>();
            int size = queue.size(); //  放在循环判断里会有问题
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                if(n.left != null) {
                    queue.offer(n.left);
                }
                if(n.right != null) {
                    queue.offer(n.right);
                }
                innerList.add(n.val);
            }
            if(!innerList.isEmpty()) {
                outerList.add(innerList);
            }
        }
        return outerList;
    }
}
